# 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现
# 次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums1 = [1,2,2,1], nums2 = [2,2]
# 输出：[2,2]
#  
# 
#  示例 2: 
# 
#  
# 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
# 输出：[4,9] 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums1.length, nums2.length <= 1000 
#  0 <= nums1[i], nums2[i] <= 1000 
#  
# 
#  
# 
#  进阶： 
# 
#  
#  如果给定的数组已经排好序呢？你将如何优化你的算法？ 
#  如果 nums1 的大小比 nums2 小，哪种方法更优？ 
#  如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 
#  
# 
#  Related Topics 数组 哈希表 双指针 二分查找 排序 👍 1070 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """
        方法1
        :param nums1:
        :param nums2:
        :return:

        d1 = {}
        d2 = {}
        re = []
        for item in nums1:
            d1[item] = d1.get(item, 0) + 1

        for item in nums2:
            d2[item] = d2.get(item, 0) + 1

        for num in set(nums1):
            if num in d1 and num in d2:
                re.extend([num] * min(d1[num], d2[num]))
                # re = re + [num] * min(d1[num], d2[num])
        return re
        """
        freq = {}
        re = []
        for num1 in nums1:
            freq[num1] = freq.get(num1, 0) + 1

        for num2 in nums2:
            if num2 in freq and freq[num2] > 0:
                re.append(num2)
                # 这一步决定了只添加两个数组里重复次数的最小次数
                freq[num2] -= 1
        return re


# leetcode submit region end(Prohibit modification and deletion)
Solution().intersect(nums1=[4, 9, 5], nums2=[9, 4, 9, 8, 4])
